class Solution:
	# @return a list of strings, [s1, s2]
	def letterCombinations(self, digits):
		d = [None,None,"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
		digits = [int(i) for i in digits]
		total = 1 if len(digits)>0 else 0
		counter = [0 for i in xrange(len(digits))]
		ans = []
		for i in digits:
			total *= len(d[i])
		i = 0
		while i < total:
			curr = ""
			for j in xrange(len(digits)):
				curr += d[digits[j]][counter[j]]
			ans.append(curr)
			carry = 1
			k = 0
			while carry and k < len(counter):
				counter[k] += 1
				if counter[k] >= len(d[digits[k]]):
					carry = 1
					counter[k] = 0
				else:
					carry = 0
				k += 1
			i += 1
		return ans

if __name__ == '__main__':
	so = Solution()
	print so.letterCombinations("23")